package com.alu.sort;

import java.util.Arrays;

public class MergeSort extends AbstractSort {
	
	// 辅助空间
	Comparable[] copyOfA;
	
	@Override
	public void sort(Comparable[] a) {
		// 一次性分配辅助空间
		this.copyOfA = new Comparable[a.length];
		// 进行排序
		this.sort(a,0,a.length-1);
	}
	
	/**
	 * 执行排序
	 * 
	 * @param a 需要归并的数组
	 * @param low 低位
	 * @param high 高位
	 */
	public void sort(Comparable[] a, int low, int high) {
		
		// 低位高位相同则返回，说明此刻传入的数组只有一个元素
		if(low >= high) return;
		
		// 计算出中间位
		int mid = low + (high-low)/2;
		
		// 分别使用递归对两个部分进行归并
		this.sort(a,low,mid); 
		this.sort(a,mid+1,high); 
		
		// 得到两个归并结束的子数组后，将两个子数组进行归并
		this.merge(a, low, mid, high);
	}
	
	
	/**
	 * 归并
	 * 
	 * @param a 需要归并的数组
	 * @param low 低位
	 * @param mid 中间位
	 * @param high 高位
	 */
	public void merge(Comparable[] a, int low, int mid, int high) {
		// 定义前半部分的起始索引
		int firstPartIndex = low;
		
		// 定义后半部分的起始索引
		int lastPartIndex = mid+1;
		
		// 进行归并
		for(int i=low; i<=high; i++) {
			// 如果前半部分用完了，则把所有后半部分的数据装入数组中
			if(firstPartIndex > mid) {
				a[i] = a[lastPartIndex++];
			}
			// 如果后半部分用完了，则把所有前半部分的数据装入数组中
			else if(lastPartIndex > high) {
				a[i] = a[firstPartIndex++];
			}
			// 如果后半部分的值小于前半部分，则将后半部分的值放入数组中
			else if(less(a[lastPartIndex], a[firstPartIndex])) {
				a[i] = a[lastPartIndex++];
			}
			// 如果前半部分的值不大于后半部分，则将前半部分的值放入数组中
			else {
				a[i] = a[firstPartIndex++];
			}
		}
		
	}
}
